package baseclass.d_list;


import utils.ListNode;
import utils.ListUtil;

/**
 * 合并2个有序链表
 * @date 2020/2/28 21:55
 */
public class Code09_MergeTwoSortedList {
    /**
     * 方式1：不改变原链表结构，额外空间O(N+M)
     * 外排或者使用堆
     */
    public static ListNode merge1(ListNode p1, ListNode p2){
        if(p1 == null || p2 == null) return p1 ==null? p2 : p1;
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while (p1 != null && p2 != null){
            if(p1.val < p2.val){
                p.next = new ListNode(p1.val);
                p1 = p1.next;
            }else {
                p.next = new ListNode(p2.val);
                p2 = p2.next;
            }
            p = p.next;
        }
        while (p1 != null){
            p.next = new ListNode(p1.val);
            p = p.next;
            p1 = p1.next;
        }
        while (p2 != null){
            p.next = new ListNode(p2.val);
            p = p.next;
            p2 = p2.next;
        }
        return head.next;
    }

    /**
     * 方式2：不需要额外空间复杂度。在原来链表上改变。
     * 递归版，空间复杂度是max(N,M)
     */
    public static ListNode merge2(ListNode p1,ListNode p2) {
        if (p1 == null || p2 == null) return p1 == null ? p2 : p1;
        ListNode node;
        if(p1.val < p2.val){
            node = p1;
            node.next = merge2(p1.next,p2);
        }else {
            node = p2;
            node.next = merge2(p1,p2.next);
        }
        return node;
    }

    public static ListNode merge3(ListNode p1,ListNode p2) {
        if (p1 == null || p2 == null) return p1 == null ? p2 : p1;
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while (p1 != null && p2 != null){
            if(p1.val < p2.val){
                p.next = p1;
                p1 = p1.next;
            }else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        p.next = p1 == null ? p2 : p1;
        return head.next;
    }
    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(12);
        head1.next.next = new ListNode(13);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(8);
        head2.next.next = new ListNode(13);
        head2.next.next.next = new ListNode(14);
        head2.next.next.next.next = new ListNode(24);

        ListNode ListNode = merge1(head1, head2);
        ListUtil.printLinkedList(ListNode);

        ListNode merge2 = merge3(head1, head2);
        ListUtil.printLinkedList(merge2);

    }

}
